Definition

This is a complexity class hierarchy, where 𝐀𝐂i\mathbf{AC}^i consists of Boolean circuits with depth O(logi⁡n)O(\log^i n) and polynomial number of unbounded fan-in AND and OR gates. (circuit complexity)

Total hierarchy of AC classes is defined as

AC=⋃i≥0ACi{\text{AC}}=\bigcup _{i\geq 0}{\text{AC}}^{i}

Examples

𝐀𝐂0\mathbf{AC}^0 complexity

#incomplete
AC⁰

See also

References

  1. https://en.wikipedia.org/wiki/AC_(complexity)
  2. https://complexityzoo.net/Complexity_Zoo:A
  3. https://en.wikipedia.org/wiki/AC0
  4. https://cstheory.stackexchange.com/questions/40408/why-is-the-circuit-class-ac0-unavoidable
  5. https://people.cs.umass.edu/~immerman/cs601/lect12.pdf
  6. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 118.